In today's modern networks, routers and other network devices are vulnerable to data packet traffic congestion. Because network traffic is typically bursty, it is not unusual for a router to be suddenly inundated with a sharp increase in traffic. Quality of service (QoS) refers to the ability of the network to handle such bursts in traffic without unacceptable loss of data packets. QoS has become increasingly important as newer Internet applications demand high bandwidth and low latency, such as in audio and video streaming or voice over internet (VOI) applications. To ensure QoS, each network device must be capable of handling such bursts in traffic, as the QoS is only as good as each of the devices on the network can provide.
In an effort to alleviate some of the traffic congestion, architects have improved the performance of Internet routers by replacing the congested shared backplanes used in conventional routers with faster switched backplanes that allow multiple packets to be transferred simultaneously. McKeown, A Fast Switched Backplane for a Gigabit Switched Router, Business Communications Review, December, 1997. Today, a high-performance Internet router typically comprises a plurality of input/output cards (“blades” herein) that receive, buffer, and transmit data packets. Using a central switched backplane, also referred to as a crossbar switch, multiple blades can communicate with each other simultaneously, enabling data packets to be sent from one blade to another across “backplane channels.”
In a typical high-performance Internet router having a switched backplane, traffic is received, buffered, and transmitted using hundreds or thousands of queues. The queues that receive the packets from other devices on the network are referred to as ingress queues and the queues transmitting the packets to other devices are referred to as egress queues. The ingress and egress queues are mapped to one another so that one or more of the ingress queues feed into one or more of the egress queues. In some cases, the ingress queues may be capable of handling packets at a faster rate than the egress queues. When the network traffic increases, the resulting congestion is typically localized at one or more of the egress queues on one of the blades, while the source of the congestion may be any of the ingress queues on the same blade or on one or more of the other blades. Conflicts can arise if more than one ingress queue wants to send a data packet to the same egress queue at the same time, or if the rate at which the ingress queue is sending packets exceeds the rate at which the egress queue can receive packets.
One drawback to using the central switched backplane is that the crossbar switch by itself has no QoS capabilities. As a result, when the traffic in the queues is transmitted across a backplane channel, the QoS policy for the packet cannot be enforced, and packets may get dropped unfairly.
FIG. 1 illustrates an example scenario of multiple ingress queues mapped to one egress queue and unfair dropping of packets from the ingress queues due to congestion. As shown, three ingress queues 110 with minimum sending rates of 5, 7, and 8 megabits per second (Mbps), respectively, are mapped to an egress queue that can only service a maximum of 20 Mbps. When some of the ingress queues experience traffic flows that cause them to simultaneously exceed their minimum sending rate, as in the illustrated example of sending 6 Mbps instead of 5 Mbps, and 10 Mbps instead of 8 Mbps, the egress queue 112 gets congested. The egress queue 112 will have to “drop” packets by dropping (6+7+10)−20=3 megabits of the 23 megabits of received traffic, which means that not all of the packets reach their intended destination. But dropping the packets is unfair since packets from all three traffic flows are dropped instead of just packets from the offending traffic flows.
One technique used to avoid such unfair dropping of packets when sending packets across the backplane channels is a time-division multiplex (TDM) scheme. In a TDM scheme, the channel's available sending time is divided into intervals, where the first ingress queue sends its packets during the first interval, the second ingress queue sends its packets during the second interval, and the third ingress queue sends its packets during the third interval, and so forth. However, the TDM scheme is inefficient, as some intervals are wasted when held open even though the corresponding ingress queue has no packet to send.
An alternative scheme to avoid dropping packets is to buffer the excess packets in the queues until there is an opportunity to send them without risk of being dropped, i.e., after the congestion has subsided and the channels are open. However, buffering the packets requires memory and memory is expensive.
Yet another alternative is to use a backpressure mechanism, where the egress queue experiencing the congestion sends feedback to the ingress queue to reduce the rate at which it is sending packets. The backpressure mechanism works well when deployed in a single chip. However, when the egress queues and ingress queues reside on different blades within the router, or even on different chips within the blade, the ability to timely communicate the feedback to the ingress queue is reduced.
Moreover, when a single ingress queue is mapped to multiple egress queues, such as when the incoming traffic on several ports of the router is aggregated together into a single ingress queue on a blade, the backpressure mechanism can result in an undesirable head-of-the-line blocking scenario. The head-of-the-line blocking scenario occurs when only one or some of the egress queues is congested, but the feedback to the single ingress queue causes all of the aggregated traffic to slow down, even traffic destined for the uncongested egress queues. A similar undesirable head-of-the-line blocking scenario occurs for multicast traffic, where the multicast traffic to all of the egress queues is slowed down, even though only one or some of the egress queues receiving the multicast traffic are experiencing congestion.